本发明涉及基于效用最优的网络分层映射及实现算法,本发明为请求服务的源端用户选择可用路径,并最优地分配路径带宽;所述算法如下:各个源端s得到其可用的多条路径P(s)、需要满足的效用U
1.基于效用最优的网络分层映射及实现算法,其特征在于:从服务到连接的多对多映射和从连接到路径的多对多映射的模型,而且通过该模型可以为请求服务的源端用户选择可用路径,并最优地分配路径带宽;所述的算法如下:步骤1,请求服务的各个源端s通过多路径发现机制得到其可用的多条路径P(s),并且得到路径的属性,如传输带宽等;步骤2,各个源端s根据各自需要满足的效用U_s,初始化自己的传输速率y_sp[t]和支付给它所使用的各个路径的代价λ_s[t];步骤3,各个源端s根据如下方程调整自己在各条路径的传输速率y_sp[t];ysp[t+1]=ysp[t]+ksysp[t](λs[t]Cp-Σr:r∈S(p)yrp[t]λr[t])yrp[t]-ϵ+,]]>步骤4,各个源端s根据如下方程调整自己支付给各条路径的代价λ_s[t];λs[t]=wsmax(η,Σp:p∈P(s)ysp[t]),]]>步骤5,服务s使用的路径p上的所有路由器配合源端在链路上为该服务预留带宽y_sp[t];步骤6,各个源端根据上述方程不断迭代直到达到映射模型的最优点,即应用层各个服务在路径上获得的最优带宽;步骤7,源端根据得到的最优带宽分配完成数据传输;步骤8,如果有新的服务请求或原有的服务已完成,那么上述迭代过程重新进行直到达到新的最优点。技术领域
本发明涉及计算机网络技术领域,特别是指一种基于效用最优的网络分层映射及实现算法。本发明考虑了多连接多路径技术在网络中的应用,从整个网络的角度考虑了路径传输带宽的分配,通过合理地分配路径的传输带宽,从而使得请求服务的源端用户的满意度达到最优。
背景技术
目前,网络技术的不断发展促使人们对各种各样服务的需求也飞速增长。为了完成一次服务,网络各个层需要维护的信息量越来越多,信息交互的方式越来越复杂,应用层的数据分割、传输层的多连接、网络层的多路径等技术已经出现并广泛应用于网络中。对于应用层,由于互联网承载的网络服务日益多样化,网络服务的内容日趋复杂,一次复杂的网络服务可以分割成多个逻辑上相互独立的部分,从而提高了服务完成的鲁棒性和灵活性;对于传输层,由于一次服务可分割成多个独立的子服务块,传输层需要为一次服务提供多条连接,利用多连接并行地传输数据,从而支持了服务的灵活分割,提高了传输的吞吐量,增强了传输的可靠性;对于网络层,各种网络接入技术的出现为通信两端多路径的建立提供了网络接入支持,形成了并行的端到端多路径通信。因此,互联网分层内部正发生重大变化,其中重要的两个就是端到端并行多连接和多路经技术,如pTCP、mTCP、SCTP、LS-SCTP、W-PR-SCTP等等。传输层利用并行多连接来传输数据可以极大地提高上层应用的吞吐量,减少应用完成的时间,提高应用完成的效率。而网络层端到端多路径技术的兴起主要得益于接入技术的多样化以及接入设备成本的不断降低。随着网络用户的不断增加,各种网络接入方式和接入技术不断涌现。比如,对于无线用户,可以通过GPRS,EDGE或3G进行广域网接入;通过Ricochet进行城域网接入;通过IEEExa0802.11、HiperLAN、蓝牙、红外等进行局域网接入;有线用户可以通过ISDN接入、ADSL接入、CableMODEM接入、光纤接入等多种技术接入互联网。另一方面,随着各种接入设备价格的逐渐下降,一台主机上有多块网络接入设备越来越平常,因此同一主机便具有了多家乡的特性,这为通信两端并行多路径的建立提供了接入支持。目前一个广泛应用的技术是利用端到端并行多路径技术来为同一个应用提供服务支持,提高传输效率和服务完成的可靠性。由于多连接多路径技术可以明显地提高传输的吞吐量和带宽的利用率,而且增强数据传输的安全性和可靠性,成为下一代互联网研究的一个重要内容。但现有技术在实现并行多连接多路径数据传输时,仅仅是根据各条路径的传输能力和拥塞状况进行数据流的分配,更侧重于网络的拥塞控制,而并没有从整个网络分层的角度来考虑如何合理最优地为服务分配路径的传输带宽,从而使得服务的满意度达到最优。如pTCP协议可以分为两部分:Stripedconnectionxa0Manager(SM)和TCP-virtual(TCP-v),前者实现了传输层的数据分割,后者探测可用路径并实现网络拥塞控制,利用探测到的多条路经来传输数据.LS-SCTP协议将SCTP的拥塞控制从面向关联扩展到面向路径,根据各条路径的拥塞程度来传输数据.
发明内容
本发明的目的在于避免上述现有技术中的不足之处而提供基于效用最优的网络分层映射及实现算法。基于网络效用最大化的思想,提出了从服务到连接的多对多映射和从连接到路径的多对多映射的模型。映射模型的主要思想是如何合理最优地为请求服务的源端用户选择可用路径,并分配路径带宽,从而使得应用层所有请求服务的源端用户的满意度达到最优。针对该模型,得到了各源端最优带宽分配的具体表达形式,而且设计了仅仅依赖于局部信息的分布式算法,该算法能够有效地收敛到映射模型的最优点,即源端用户获得的全局最优带宽分配。本发明的目的可以通过以下措施来达到:基于效用最优的网络分层映射及实现算法,从服务到连接的多对多映射和从连接到路径的多对多映射的模型,为请求服务的源端用户选择可用路径,分配路径带宽;所述的算法如下:步骤1,请求服务的各个源端s通过多路径发现机制得到其可用的多条路径P(s),并且得到路径的属性;步骤2,各个源端s根据各自需要满足的效用U_s,初始化自己的传输速率y_sp[t]和支付给它所使用的各个路径的代价λ_s[t];步骤3,各个源端s根据如下方程调整自己在各条路径的传输速率y_sp[t];ysp[t+1]=ysp[t]+ksysp[t](λs[t]Cp-Σr:r∈S(p)yrp[t]λr[t])yrp[t]-ϵ+,]]>步骤4,各个源端s根据如下方程调整自己支付给各条路径的代价λ_s[t];λs[t]=wsmax(η,Σp:p∈P(s)ysp[t]),]]>步骤5,服务s使用的路径p上的所有路由器配合源端在链路上为该服务预留带宽y_sp[t];步骤6,各个源端根据上述方程迭代直到达到映射模型的最优点,即应用层各个服务在路径上获得的最优带宽;步骤7,源端根据得到的最优带宽分配完成数据传输;步骤8,如果有新的服务增加进来或者原有的服务完成了,那么上述迭代过程重新进行直到达到新的最优点。本发明相比现有技术具有如下优点:本发明从理论上阐述了网络分层映射的目标,即请求服务的用户的满意度达到最优,指出了映射时受到的约束,即各条路径的传输能力。在此基础上得到了分层映射的理论模型,并得到了各源端获得的最优带宽分配的具体形式。更为重要的是,设计了一种仅依赖于局部可用信息的分布式算法,该算法能够收敛到映射模型的最优点,即请求服务的源端用户所获得的全局最优带宽分配。
附图说明
图1是基于效用最优的分层映射模型的反馈系统。图2是协议栈和映射参数的关系图。图3是映射算法的流程图。具体实施例本发明基于网络效用最大化的思想研究了网络分层和映射,给出了从服务到多连接和从多连接到多路径的映射模型,指出了应用层的服务通过多连接再映射到多路径所要实现的目标,就是通过合理有效地选择连接与路径并分配路径带宽,实现请求服务的源端用户的效用之和达到最优。而且,本发明设计了一种仅依赖于局部信息的分布式映射算法,可以有效的实现映射模型的最优点,即请求服务的各个源端在其使用的多条路径上的最优带宽分配。服务到连接的映射模型1.映射关系某服务利用服务分割技术后,形成多个子服务块,而对每个子服务块均可以通过建立的多条连接来传输,因此从服务到连接的映射是多对多的。这种多对多映射实现了一个服务可以由多个连接来完成,提高了服务完成的效率;同时,通过流分类可以使同一种类型的数据利用同一个连接进行传输,提高了连接的利用率。假设每个源端用户各请求一次服务,而应用层需要完成的服务的集合为S,其元素是各个服务s。简单起见,令请求服务的网络源端用户集合也是S,每个源端请求一次服务。连接的集合为C,其元素是可以为所有服务建立的各个连接c。从一个服务到多个连接的映射意味着某个服务s∈S需要由多个连接c∈C完成,即服务提供者同时提供多个连接完成某个服务;从多个服务到多个连接的多对多映射意味着每个服务s都由多个连接c完成,每个连接c为多个服务s传输数据,因为各个服务经过流分类后,不同类型的数据流通过不同的连接传输。令S(c)是使用某条连接c的所有服务的集合,C(s)是某个服务s使用的所有连接的集合。因此s∈S(c)当且仅当c∈C(s),即某个服务s使用了某个连接c进行传输。2.映射模型源端用户在获得服务时都想使得自己的满意度达到最优,而满意度可以用效用函数来刻画。从整个网络应用层的角度考虑,就是使得请求服务的所有源端的满意度达到最优。所以,应用层的映射目标其实就是最大化源端用户的聚合效用,即max∑_sU_s(z_s),其中U_s(z_s)是请求服务的源端当获得的带宽是z_s时的效用。经过从服务到连接的映射后,服务的数据流进行流分类,形成多个连接流进行传输,每个连接流都可能传输某服务的数据流。假设服务s经分流之后在连接c上获得的流量分配为x_sc,则一定满足z_s=∑_c:c∈C(s)x_sc。从服务到连接的映射目标其实就是如何合理地将服务的数据流经过流分类后,映射到各个连接上进行数据传输,从而使得所有服务的效用函数之和达到最优。从网络效用最优的角度考虑,服务到连接的映射模型具有下述形式:ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="533"/>其中Φ就是从服务到连接的映射函数,该映射函数的功能是针对每个服务实现了多连接的建立和传输,并将服务的数据流分配到各个连接上。连接到路径的映射模型1.映射关系应用层中各个服务经由服务到连接的映射后,形成多个连接来传输应用层的数据。而通过连接到路径的映射后,形成了多条端到端的路径,实现了一个连接可以选择多条路径进行数据传输,提高了数据传输效率;同时,多个连接也可以选择同一条路径进行数据传输,提高该路径的利用率。假设网络中路径的集合是P,元素是网络层中可以为连接提供支持的各条路径p。从一个连接到多条路径的一对多映射意味着某连接c∈C选择多条路径p∈P来完成数据传输,提高了数据传输速率和效率,如有线、无线等多种通信方式形成的多条路径同时传输数据;从多个连接到一条路径的多对一映射意味着多个连接c∈C选择一条路径p∈P来完成数据传输,提高了该路径的利用率;从多个连接到多个路径的多对多映射意味着多个连接c∈C由多条路径p∈P完成,提高了数据传输的效率和路径的利用率,增强了传输的可靠性和安全性。2.路径选择服务的数据流经过流分类后,形成各个连接的数据流,这些连接流映射成路径数据流后在网络层进行传输。数据流从连接到路径的多对多映射可以用映射矩阵A=(α_cp)_C×P来表示,矩阵元素α_cp∈{0,1}代表连接c是否利用路径p传输数据,或者说路径p是否支持连接c。若α_cp=1,则连接c利用路径p传输数据;否则a_cp=0,则连接c不利用路径p传输数据。假设服务s在路径p上获得的带宽分配为y_sp,则y_sp=∑_cx_scα_cp,写成矩阵的形式为其中x_sc是服务s经过分流之后在连接c上获得的流量分配。因此,经过上述两次映射后,服务的数据流要选择合适的路径进行传输。令S(p)是使用路径p的所有服务的集合,P(s)是服务s使用的所有路径的集合。因此s∈S(p)当且仅当p∈P(s),即服务s使用了路径p来传输数据,或者该条路径p为服务s传输数据。3.映射模型从连接到路径的映射其实就是通过将连接映射到各条路径,有效地为服务分配路径带宽,从而使得请求服务的源端用户满足一定的要求。路径的传输能力是受到该路径上瓶颈链路的带宽限制的,所以定义某条路径的带宽就是该条路径上瓶颈链路的带宽。在映射的过程中,所有服务在路径p上获得的带宽分配之和不能超过该路径的带宽,即∑_s:s∈S(p)y_sp≤C_p;同时,某服务经过两次映射后,在各条路径上得到的带宽分配应该等于其服务的数据流大小,即∑_p:p∈P(s)y_sp=z_s,这里z_s是服务s的数据流大小,即该服务获得的总的服务带宽.通过上述的两次映射后,从服务到路径的映射目标是在合理选择有效路径后,使得请求服务的源端用户的满意度达到最优.因此,从连接到路径的映射模型具有下述形式:ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="533"/>其中Ψ就是从连接到路径的映射函数,该映射函数的功能是为连接选择合适的路径进行路由,并以最优的方式将路径带宽分配给请求服务的各个源端。综上所述,是基于效用最优的分层映射模型的反馈系统如图1所示。应用层要实现所有请求服务的源端用户的效用达到最优,在传输层通过建立多条连接将源端用户的传输速率分配到多条并行连接上;多个连接可以在同一条路径上进行路由,同一个连接也可以在多条路径上进行路由,路径选择完成之后,源端用户的传输速率就分配到了多条并行路径上,同时,由于路径的传输能力是一定的,因此网络层拥塞程度及时通知源端用户调整传输速率。因此,为源端用户最优分配路径带宽的过程其实就是个反馈控制系统,也正如图1所示。映射算法针对上述的从服务到路径的映射模型,通过分析优化问题P就可以得到映射的最优带宽分配,而且提出分布式的映射算法,该映射算法的平衡点就是映射模型的最优点。1.映射模型分析选取效用函数U_s(z_s)=w_slogz_s,该效用函数可以表示为每个服务的端到端吞吐量,而且还可以用来反应获得服务的源端之间的公平性,w_s是获得服务的源端为该服务提出的支付成本,也可以理解为源端的权重。由非线性规划的理论可知,映射模型是一个凸规划问题,该问题的最优解是存在的。映射模型P的拉格朗日函数为L‾(y,z;λ,μ)=ΣsUs(zs)+Σsλs(Σp:p∈P(s)ysp(t)-zs)+Σpμp(Cp-Σs:s∈S(p)ysp-δp2)---(1)]]>其中λ_s≥0,μ_p≥0是拉格朗日因子,可以理解为获得该服务的源端所支付价格和路径索取的价格。令ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="304"/>则μ_p=0或者δ_p=0。若μ_p=0,则不等式约束就是不积极约束,因此可以忽略;若δ_p=0,则约束是积极约束。在映射过程中,因为每个源端在请求服务时总是想最大化自己的效用,只要至少有一个服务使用了某条路径,那么这条路径的约束就会是积极的,后面的分析中不妨假设δ_p=0。令ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="338"/>则λ_s=U′_s(z_s)=w_s/z_s。拉格朗日函数(1)可以写为L(y;μ)=ΣsUs(Σp:p∈P(s)ysp)+Σpμp(Cp-Σs:s∈S(p)ysp)]]>=ΣsUs(Σp:p∈P(s)ysp)+ΣpμpCp-ΣpμpΣs:s∈S(p)ysp]]>=Σs∈SUs(Σp:p∈P(s)ysp)+Σp∈PμpCp-Σs∈SΣp:p∈P(s)μpysp=Σs∈S(Us(Σp:p∈P(s)ysp)-Σp:p∈P(s)μpysp)+Σp∈PμpCp,---(2)]]>令ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="458"/>则ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="262"/>所以,若p,q∈P(s),则μ_p=μ_q,即某服务所使用的各条路径的代价都是相等的。同时,由于λ_s=U′_s(z_s)=w_s/z_s,所以当映射模型达到最优带宽分配时,某服务使用的多条路径的代价都等于该服务所支付的代价。此时,由于ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="310"/>及μ_p=μ,拉格朗日函数(2)可以写为L(y;μ)=Σs∈S(Us(Σp:p∈P(s)ysp)-μΣp:p∈P(s)ysp)+μΣp∈PCp=Σs∈S(wslogwsμ-μwsμ)+μΣp∈PCp,]]>令dL(y;μ)dμ=0,]]>则μ=Σs∈SwsΣp∈PCp.---(3)]]>由于λ_s=w_s/z_s=μ_p=μ,所以,zs=wsΣp∈PCpΣs∈Sws.---(4)]]>因此,映射模型的全局最优带宽分配是存在的,并且某服务所使用的各条路径的代价都是相等的,这是符合实际情况的。代价可以理解为路径上的传输时延,丢包率等等,某服务不断探测它所使用的各条路径,总是尽量优先选择代价小的路径来传输数据包,因此当达到平衡点的时候,该服务所使用的各条路径上的代价都是相等的。2.映射算法为了能够在分布式环境中,得到映射模型的全局最优解,设计了一种分布式算法,该算法仅仅依赖于局部信息,通过迭代达到映射模型的最优带宽分配。分布式算法1:ddtysp(t)=ksysp(t)(λs(t)Cp-Σr:r∈S(p)yrp(t)λr(t))yrp(t)-ϵ+,---(5)]]>λs(t)=wsmax(η,Σp:p∈P(s)ysp(t)),---(6)]]>其中,ε,η>0是常数,k_s是迭代步长,y_sp(t)是服务s在路径p上的数据流大小,λ_s(t)是源端支付的代价,C_p是路径p的传输容量。函数a=(b)_c⁺表示当c>0时a=b,而当c=0时a=max(0,b)。所以,服务获得的速率y_rp(t)不会低于ε,保证了服务开始探索它的传输速率时不至于一直停留在零点。对于某个服务也给定了代价的界值,若该服务获得的总的速率很小时,η保证了源端支付的代价不高于界值w_s/η。该算法中,某服务仅仅需要知道它所使用的路径,以及使用这些路径的其他服务即可,并不需要知道网络中所有需要完成的服务和所有路径的信息,因此该算法仅依赖于局部信息,所以该算法是分布式。分析该算法的平衡点,令(5)为零,则可以得到λs*=Σr:r∈S(p)yrp*λr*Cp,λs*wsΣp:p∈P(s)ysp*,---(7)]]>而且Σp∈PCp=Σp∈PΣr:r∈S(p)ysp*λr*λs*=1λs*Σr∈SΣp:p∈P(r)yrp*λr*=1λs*Σr∈Sλr*Σp:p∈P(r)yrp*=(a)1λs*Σr∈Swr=zs*wsΣr∈Swr,]]>其中等式(a)由(7)得到,则zs*=wsΣp∈PCpΣs∈Sws,λs*=Σr∈SwrΣp∈PCp]]>所以,该算法的平衡点正好就是映射模型的最优点,也就是最优带宽分配。因此,当网络中的源端用户利用多连接多路径来传输某服务的数据时,网络的协议栈与映射参数之间的关系如图2所示。其中,U_s是请求服务的源端用户的效用函数,z_s是源端获得的总的带宽大小,y_sp是源端在路径p上获得带宽分配,λ_s是源端支付给路径的价格,μ_p是路径收取的价格。上述给出的是算法的连续形式,实际上,在具体的网络实现中,算法的实现是离散形式进行的,所以,也给出了下述的离散形式的算法。分布式算法2:ysp[t+1]=ysp[t]+ksysp[t](λs[t]Cp-Σr:r∈S(p)yrp[t]λr[t])yrp[t]-ϵ+,---(8)]]>λs[t]=wsmax(η,Σp:p∈P(s)ysp[t]),---(9)]]>该离散形式的算法也是收敛的,而且收敛到映射模型的最优点。
具体实施方式
下面给出本发明的实施例,并结合附图对本发明的实施例进一步说明。实施例;如图3所示,本发明提出的分布式算法的具体实现步骤如下。步骤1,请求服务的各个源端s通过多路径发现机制得到其可用的多条路径P(s),并且得到路径的属性,如传输容量C_p等等;步骤2,各个源端s根据各自需要满足的效用U_s,初始化自己的传输速率y_sp[t]和支付给它所使用的各个路径的代价λ_s[t];步骤3,各个源端s根据方程(8)调整自己在各条路径的传输速率y_sp[t];步骤4,各个源端s根据方程(9)调整自己支付给各条路径的代价λ_s[t];步骤5,服务s使用的路径p上的所有路由器配合源端在链路上为该服务预留带宽y_sp[t];步骤6,各个源端根据(8)(9)迭代直到达到映射模型的最优点,即应用层各个服务在路径上获得的最优带宽;步骤7,源端根据得到的最优带宽分配完成数据传输;步骤8,如果有新的服务增加进来或者原有的服务完成了,那么上述迭代过程重新进行直到达到新的最优点。